//
//  cutils.c
//  OJ
//
//  Created by wangrui on 14-9-19.
//  Copyright (c) 2014年 PPS. All rights reserved.
//

#include "cutils.h"
#include <stdlib.h>

void printArray(int a[], int count)
{
	for (int k=0; k<count; k++) {
		printf("%d ",a[k]);
	}
	
	printf("\n");
}

void swap(int *a, int  *b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

//====================================
//========== Queue ===================
//====================================
void init_queue(queue_t *q)
{
	queue_t init = (queue_t)malloc(sizeof(struct Queue));
	
	*q = init;
	(*q)->head = *q;
	(*q)->tail = *q;
	(*q)->init = *q;
	(*q)->next = NULL;
}

void destory_queue(queue_t q)
{
	queue_t temp = q;
	while (temp != NULL) {
		free(temp);
		temp = temp->next;
	}
}

void enqueue(queue_t q, void *data)
{
	queue_t new = (queue_t)malloc(sizeof(struct Queue));
	new->head = NULL;
	new->tail = NULL;
	new->data = data;
	new->next = NULL;
	
	q->tail->next = new;
	q->tail = new;
	
	if (is_empty_queue(q)) {
		q->head = new;
	}
}


void* const get_head(queue_t q)
{
	if (is_empty_queue(q)) {
		
		return NULL;
	}
	
	return q->head->data;
}

void * const get_tail(queue_t q)
{
	if (is_empty_queue(q)) {
		
		return NULL;
	}
	
	return q->tail->data;
}


void * dequeue(queue_t q, int *status){
	
	if (is_empty_queue(q)) {
		
		if (status != NULL) {
			*status = 0;
		}
		return NULL;
	}
	
	queue_t out = q->head;
	void *ret = out->data;
	
	q->head = q->head->next;
	if (q->head == NULL) {//出队列的是最后一个元素
		q->head = q->init;
		q->tail = q->init;
		q->next = NULL;
	}
	
	free(out);
	
	if (status != NULL) {
		*status = 1;
	}
	
	return ret;
}

int is_empty_queue(queue_t q)
{
	if (q->head == q->init) {
		return 1;
	}
	
	return 0;
}



//========================================
//============Stack=======================
//========================================


c_stack_t createStack(){
	c_stack_t s = (c_stack_t)malloc(sizeof(struct Stack));
	struct StackNode *headNode = (struct StackNode *)malloc(sizeof(struct StackNode));
	
	s->head = headNode;
	s->tail = headNode;
	
	s->head->next = NULL;
	s->head->pre = NULL;
	s->tail->pre = NULL;
	s->tail->next = NULL;
	
	return s;
}

void destory_tack(c_stack_t stack){
	if (stack) {
		
		struct StackNode *head = stack->head;
		
		while (head) {
			free(head);
			head = head->next;
		}
		
		free(stack);
	}
}

void push(c_stack_t stack,void *data){
	
	struct StackNode *newNode = (struct StackNode *)malloc(sizeof(struct StackNode));
	
	newNode->data = data;
	newNode->next = NULL;
	newNode->pre = stack->tail;
	
	if (is_empty_stack(stack)) {
		stack->head->next = newNode;
	}
	
	stack->tail->next = newNode;
	stack->tail = newNode;
}

void * pop(c_stack_t stack){
	if (is_empty_stack(stack)) {
		return NULL;
	}
	
	struct StackNode *out = stack->tail;
	void *ret = out->data;
	
	stack->tail = out->pre;
	stack->tail->next = NULL;
	
	free(out);
	
	if (is_empty_stack(stack)) {
		stack->head->next = NULL;
	}
	
	return ret;
}

int is_empty_stack(c_stack_t stack){
	return stack->head == stack->tail;
}





